package Set_and_Dict;

/*
存在重复元素 III
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)：
i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
示例 2：
输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/all-about-lockup-table/xhw24c/
 */

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class _52存在重复元素3_ {
    public static void main(String[] args) {

    }

    //官解：滑动窗口
    //新方法  TreeSet  ceiling()
        public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
            int n = nums.length;
            TreeSet<Long> set = new TreeSet<>();
            for (int i = 0; i < n; i++) {
                //ceiling()方法用于返回等于或大于给定元素(ele)的最低元素(如果存在)，否则返回null。
                //正好将绝对值囊括了
                Long ceiling = set.ceiling((long) nums[i] - (long) valueDiff);
                if (ceiling != null && ceiling <= (long) nums[i] + (long) valueDiff) {
                    return true;
                }
                set.add((long) nums[i]);
                if (i >= indexDiff) {
                    set.remove((long) nums[i - indexDiff]);
                }
            }
            return false;
        }

    //官解：桶排序 *
    class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            int n = nums.length;
            Map<Long, Long> map = new HashMap<Long, Long>();
            long w = (long) t + 1;
            for (int i = 0; i < n; i++) {
                long id = getID(nums[i], w);
                if (map.containsKey(id)) {
                    return true;
                }
                if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                    return true;
                }
                if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                    return true;
                }
                map.put(id, (long) nums[i]);
                if (i >= k) {
                    map.remove(getID(nums[i - k], w));
                }
            }
            return false;
        }

        public long getID(long x, long w) {
            if (x >= 0) {
                return x / w;
            }
            return (x + 1) / w - 1;
        }
    }


}
